The problem of scheduling different jobs sharing a common resource occurs in many different contexts. In the most general terms it can be formulated as follows:
A single resource of some kind is shared by several entities indexed by integers i=1,2, . . . n. Every entity has a rate R(i) associated with it. The rates are assigned in such a way that sum of all R(i) does not exceed the capacity of the resource. For example, in computer networks the entity is an individual flow, and the shared resource may be a bottleneck communications link or a server capacity. The entities can be served in some service increments, one at a time. For example, the service increment for a network flow is one packet (or cell, in the ATM terminology). A device, called the Scheduler, needs to determine the order of service for different entities so that the average service rate received by an entity is its assigned rate R(i). Aside from guaranteeing the long-term average rate, an important goal is to bound the discrepancy between the ideal and the actual service times of each individual service increment, i.e., each packet of each flow.
An example of an environment where such a problem occurs is a processor which must schedule jobs competing for its cycles. If all jobs are of equal importance, then it is desirable to provide all jobs an equal share of the processor capacity. If however, the jobs have different importance, a possible strategy is to assign weights to all jobs corresponding to their importance, and provide each job a share of processor capacity proportional to the weight assigned to the job. In this case the desired service rates are determined by the weights of the jobs. An alternative approach might be to assign rates to jobs according to some other rule, which is specific to a particular policy and environment of the problem. For example, a rule might be to give some fixed allocation to high priority jobs and then share the remaining bandwidth among low priority jobs.
As mentioned earlier, another example when a similar problem might occur is in computer networks. For example, in ATM networks there is usually some rate associated with every flow traversing the network. This rate can be either the result of negotiation with the network at setup time, as for example for Constant Bit Rate (CBR) traffic, or can be the result of a traffic management feedback control scheme as is the case for Available Bit Rate (ABR) traffic. The set of rates can be either relatively static, as for long-term CBR flows, or may change quickly in response to congestion as in the case of ABR flows.
Even if the rates are not assigned explicitly, which is the case, for example, in many packet-switching networks, different flows may be of different importance. For example, one flow may be a compound flow of data from 1000 users, while another flow may represent a single user. It may be reasonable in such a case to assign weights to different flows given their relative importance. If the total demand of flows exceeds the capacity of the bottleneck resource, typically a communication link, then a possible policy is to service all flows proportionally to their weights as described earlier in the example of processor sharing. This effectively assigns rates to the flows.
In recent years, rate-based scheduling disciplines at the switching points in computer networks have received much attention. A comprehensive review of such schemes can be found in Hui Zhang, Service Disciplines for Guaranteed Performance in Packet-Switching Networks, Proceedings IEEE, October 1995. These schemes generally are applicable at network switches and can guarantee rates assigned to the flows.
The problem of scheduling of different flows in computer networks exists not only for the switches in the network, but in host adapters as well. For example, an adapter in an ATM network must schedule different flows, each of which has a rate associated with it. Typically, the CBR flows are serviced at a higher priority according to a pre-computed schedule. One of the disadvantages of pre-computing the CBR schedule is that because it is computed without taking any non-CBR flows into account, the service of non-CBR flows may be unnecessarily adversely affected by the CBR bursts. Pre-computing the schedule also has the disadvantage that it is computationally expensive and is usually done in software on a slow time scale. While this may be acceptable for CBR flows which only need to perform this once a new connection is established, it is not feasible if many flows with frequently changing rates need to be scheduled.
Another scheme that is known for rate-based scheduling is the so-called Leaky Bucket, described for example in The ATM Forum Traffic Management Specification Version 4.0. The scheme requires a large amount of per flow state and therefore is prohibitive for a large number of flows.
Also frequently used is the so called "time-wheel" or "calendar queue" approach. An example of the calendar queue approach may be found in Brown., R, Calendar Queue: A fast O(1) priority queue implementation for the simulation even set problem, Communications of the ACM, vol.31, pp.1220-1227. Unlike the Leaky Bucket scheme, the calendar queues are simple to implement. Unfortunately, in general the calendar queue approach cannot guarantee that the long-term average rate achieved by a flow is equal to its assigned rate.
Therefore, it is desirable to design a scheme that may be used for rate-based scheduling of flows with dynamically changing rates at networks adapters and that can guarantee the assigned rate of the flows.
It is also desirable that this scheme be of use for CBR-type traffic (also known as "guaranteed service" in packet switching networks) and ABR-type traffic (also known as adaptive traffic) simultaneously, as well as VBR (variable bit rate) traffic in ATM networks (also known as predictive traffic in packet switching networks). Finally it is desirable that this scheme be useful in the more general context of rate-based scheduling as described earlier.
What is needed is a general approach to rate scheduling that will work in many different environments. In particular, the new approach should work well for network adapters as well as for network switches.
The approaches described in the paper by Hui Zhang for switch scheduling are not easily applicable to adapters. One of the reasons for this is that most of the scheduling schemes for switches rely on packet arrival times to the switch to determine the scheduling order of packets from different flows. The notion of arrival time is not always well-specified for the adapter
A new scheme, referred to as the Relative Error (RE) Scheduler, was described in copending U.S. patent application Ser. No. 08/579,393. The RE scheme has several appealing properties, the most important of which is that the descrepancy between the ideal transmission time of any cell and its actual transmission time is bounded, thereby providing a stringent rate guarantee for any flow.
However, the RE scheme as described in U.S. patent application Ser. No. 08/579,393 required finding the maximum of n numbers (where n is the number of flows to be scheduled), all of which had to be updated at each step of the method. Thus, complexity of the RE scheme is O(n), where n is the number of flows to be scheduled. In addition, RE requires that the rates assigned to different jobs be pre-scaled so that the sum of all rates does not exceed the service capacity. Therefore, any time a change of some flow rate cause infeasibility of the total set of rates, the rates of all flows may need to be recalculated to ensure feasibility. Scheduling decisions (especially when scheduling flows in high-speed networks), must be made in a very short time (typically of the order of a few microseconds). A scheduler may need to support thousands of flows, which makes the task of quickly scanning and updating entries corresponding to each flow extremely difficult. Therefore, reducing the computational complexity of the scheme is very important.
The present invention describes two ways of reducing the complexity of the RE scheme:
a) by reducing the amount of state that needs to be scanned at each cell time by means of the discrete rate approach PA1 b) by providing means for on-line proportional scaling of the flow rates up or down to the link capacity.
The latter allows not only avoiding the extra work needed to make sure that the rates do not exceed the link bandwidth but can be optionally used to proportionally increase the service rate of all flows if the sum of the nominal requested rates of all flows is less than the available bandwidth.